home *** CD-ROM | disk | FTP | other *** search
/ Aminet 25 / Aminet 25 (1998)(GTI - Schatztruhe)[!][Jun 1998].iso / Aminet / game / shoot / ADoom_src_1_2.lha / ADoom_src / r_bsp.c < prev    next >
C/C++ Source or Header  |  1998-02-14  |  11KB  |  580 lines
  1. // Emacs style mode select   -*- C++ -*- 
  2. //-----------------------------------------------------------------------------
  3. //
  4. // $Id:$
  5. //
  6. // Copyright (C) 1993-1996 by id Software, Inc.
  7. //
  8. // This source is available for distribution and/or modification
  9. // only under the terms of the DOOM Source Code License as
  10. // published by id Software. All rights reserved.
  11. //
  12. // The source is distributed in the hope that it will be useful,
  13. // but WITHOUT ANY WARRANTY; without even the implied warranty of
  14. // FITNESS FOR A PARTICULAR PURPOSE. See the DOOM Source Code License
  15. // for more details.
  16. //
  17. // $Log:$
  18. //
  19. // DESCRIPTION:
  20. //    BSP traversal, handling of LineSegs for rendering.
  21. //
  22. //-----------------------------------------------------------------------------
  23.  
  24.  
  25. static const char
  26. rcsid[] = "$Id: r_bsp.c,v 1.4 1997/02/03 22:45:12 b1 Exp $";
  27.  
  28.  
  29. #include "doomdef.h"
  30.  
  31. #include "m_bbox.h"
  32.  
  33. #include "i_system.h"
  34.  
  35. #include "r_main.h"
  36. #include "r_plane.h"
  37. #include "r_things.h"
  38.  
  39. // State.
  40. #include "doomstat.h"
  41. #include "r_state.h"
  42.  
  43. //#include "r_local.h"
  44.  
  45.  
  46.  
  47. seg_t*        curline;
  48. side_t*        sidedef;
  49. line_t*        linedef;
  50. sector_t*    frontsector;
  51. sector_t*    backsector;
  52.  
  53. FAR drawseg_t    drawsegs[MAXDRAWSEGS];
  54. drawseg_t*    ds_p;
  55.  
  56. void
  57. R_StoreWallRange
  58. ( int    start,
  59.   int    stop );
  60.  
  61.  
  62.  
  63.  
  64. //
  65. // R_ClearDrawSegs
  66. //
  67. void R_ClearDrawSegs (void)
  68. {
  69.     ds_p = drawsegs;
  70. }
  71.  
  72.  
  73.  
  74. //
  75. // ClipWallSegment
  76. // Clips the given range of columns
  77. // and includes it in the new clip list.
  78. //
  79. typedef    struct
  80. {
  81.     int    first;
  82.     int last;
  83.     
  84. } cliprange_t;
  85.  
  86.  
  87. #define MAXSEGS        32
  88.  
  89. // newend is one past the last valid seg
  90. cliprange_t*    newend;
  91. FAR cliprange_t    solidsegs[MAXSEGS];
  92.  
  93.  
  94.  
  95.  
  96. //
  97. // R_ClipSolidWallSegment
  98. // Does handle solid walls,
  99. //  e.g. single sided LineDefs (middle texture)
  100. //  that entirely block the view.
  101. // 
  102. void
  103. R_ClipSolidWallSegment
  104. ( int            first,
  105.   int            last )
  106. {
  107.     cliprange_t*    next;
  108.     cliprange_t*    start;
  109.  
  110.     // Find the first range that touches the range
  111.     //  (adjacent pixels are touching).
  112.     start = solidsegs;
  113.     while (start->last < first-1)
  114.     start++;
  115.  
  116.     if (first < start->first)
  117.     {
  118.     if (last < start->first-1)
  119.     {
  120.         // Post is entirely visible (above start),
  121.         //  so insert a new clippost.
  122.         R_StoreWallRange (first, last);
  123.         next = newend;
  124.         newend++;
  125.         
  126.         while (next != start)
  127.         {
  128.         *next = *(next-1);
  129.         next--;
  130.         }
  131.         next->first = first;
  132.         next->last = last;
  133.         return;
  134.     }
  135.         
  136.     // There is a fragment above *start.
  137.     R_StoreWallRange (first, start->first - 1);
  138.     // Now adjust the clip size.
  139.     start->first = first;    
  140.     }
  141.  
  142.     // Bottom contained in start?
  143.     if (last <= start->last)
  144.     return;            
  145.         
  146.     next = start;
  147.     while (last >= (next+1)->first-1)
  148.     {
  149.     // There is a fragment between two posts.
  150.     R_StoreWallRange (next->last + 1, (next+1)->first - 1);
  151.     next++;
  152.     
  153.     if (last <= next->last)
  154.     {
  155.         // Bottom is contained in next.
  156.         // Adjust the clip size.
  157.         start->last = next->last;    
  158.         goto crunch;
  159.     }
  160.     }
  161.     
  162.     // There is a fragment after *next.
  163.     R_StoreWallRange (next->last + 1, last);
  164.     // Adjust the clip size.
  165.     start->last = last;
  166.     
  167.     // Remove start+1 to next from the clip list,
  168.     // because start now covers their area.
  169.   crunch:
  170.     if (next == start)
  171.     {
  172.     // Post just extended past the bottom of one post.
  173.     return;
  174.     }
  175.     
  176.  
  177.     while (next++ != newend)
  178.     {
  179.     // Remove a post.
  180.     *++start = *next;
  181.     }
  182.  
  183.     newend = start+1;
  184. }
  185.  
  186.  
  187.  
  188. //
  189. // R_ClipPassWallSegment
  190. // Clips the given range of columns,
  191. //  but does not includes it in the clip list.
  192. // Does handle windows,
  193. //  e.g. LineDefs with upper and lower texture.
  194. //
  195. void
  196. R_ClipPassWallSegment
  197. ( int    first,
  198.   int    last )
  199. {
  200.     cliprange_t*    start;
  201.  
  202.     // Find the first range that touches the range
  203.     //  (adjacent pixels are touching).
  204.     start = solidsegs;
  205.     while (start->last < first-1)
  206.     start++;
  207.  
  208.     if (first < start->first)
  209.     {
  210.     if (last < start->first-1)
  211.     {
  212.         // Post is entirely visible (above start).
  213.         R_StoreWallRange (first, last);
  214.         return;
  215.     }
  216.         
  217.     // There is a fragment above *start.
  218.     R_StoreWallRange (first, start->first - 1);
  219.     }
  220.  
  221.     // Bottom contained in start?
  222.     if (last <= start->last)
  223.     return;            
  224.         
  225.     while (last >= (start+1)->first-1)
  226.     {
  227.     // There is a fragment between two posts.
  228.     R_StoreWallRange (start->last + 1, (start+1)->first - 1);
  229.     start++;
  230.     
  231.     if (last <= start->last)
  232.         return;
  233.     }
  234.     
  235.     // There is a fragment after *next.
  236.     R_StoreWallRange (start->last + 1, last);
  237. }
  238.  
  239.  
  240.  
  241. //
  242. // R_ClearClipSegs
  243. //
  244. void R_ClearClipSegs (void)
  245. {
  246.     solidsegs[0].first = -0x7fffffff;
  247.     solidsegs[0].last = -1;
  248.     solidsegs[1].first = viewwidth;
  249.     solidsegs[1].last = 0x7fffffff;
  250.     newend = solidsegs+2;
  251. }
  252.  
  253. //
  254. // R_AddLine
  255. // Clips the given segment
  256. // and adds any visible pieces to the line list.
  257. //
  258. void R_AddLine (seg_t*    line)
  259. {
  260.     int            x1;
  261.     int            x2;
  262.     angle_t        angle1;
  263.     angle_t        angle2;
  264.     angle_t        span;
  265.     angle_t        tspan;
  266.     
  267.     curline = line;
  268.  
  269.     // OPTIMIZE: quickly reject orthogonal back sides.
  270.     angle1 = R_PointToAngle (line->v1->x, line->v1->y);
  271.     angle2 = R_PointToAngle (line->v2->x, line->v2->y);
  272.     
  273.     // Clip to view edges.
  274.     // OPTIMIZE: make constant out of 2*clipangle (FIELDOFVIEW).
  275.     span = angle1 - angle2;
  276.     
  277.     // Back side? I.e. backface culling?
  278.     if (span >= ANG180)
  279.     return;        
  280.  
  281.     // Global angle needed by segcalc.
  282.     rw_angle1 = angle1;
  283.     angle1 -= viewangle;
  284.     angle2 -= viewangle;
  285.     
  286.     tspan = angle1 + clipangle;
  287.     if (tspan > 2*clipangle)
  288.     {
  289.     tspan -= 2*clipangle;
  290.  
  291.     // Totally off the left edge?
  292.     if (tspan >= span)
  293.         return;
  294.     
  295.     angle1 = clipangle;
  296.     }
  297.     tspan = clipangle - angle2;
  298.     if (tspan > 2*clipangle)
  299.     {
  300.     tspan -= 2*clipangle;
  301.  
  302.     // Totally off the left edge?
  303.     if (tspan >= span)
  304.         return;    
  305.     angle2 = -clipangle;
  306.     }
  307.     
  308.     // The seg is in the view range,
  309.     // but not necessarily visible.
  310.     angle1 = (angle1+ANG90)>>ANGLETOFINESHIFT;
  311.     angle2 = (angle2+ANG90)>>ANGLETOFINESHIFT;
  312.     x1 = viewangletox[angle1];
  313.     x2 = viewangletox[angle2];
  314.  
  315.     // Does not cross a pixel?
  316.     if (x1 == x2)
  317.     return;
  318.     
  319.     backsector = line->backsector;
  320.  
  321.     // Single sided line?
  322.     if (!backsector)
  323.     goto clipsolid;        
  324.  
  325.     // Closed door.
  326.     if (backsector->ceilingheight <= frontsector->floorheight
  327.     || backsector->floorheight >= frontsector->ceilingheight)
  328.     goto clipsolid;        
  329.  
  330.     // Window.
  331.     if (backsector->ceilingheight != frontsector->ceilingheight
  332.     || backsector->floorheight != frontsector->floorheight)
  333.     goto clippass;    
  334.         
  335.     // Reject empty lines used for triggers
  336.     //  and special events.
  337.     // Identical floor and ceiling on both sides,
  338.     // identical light levels on both sides,
  339.     // and no middle texture.
  340.     if (backsector->ceilingpic == frontsector->ceilingpic
  341.     && backsector->floorpic == frontsector->floorpic
  342.     && backsector->lightlevel == frontsector->lightlevel
  343.     && curline->sidedef->midtexture == 0)
  344.     {
  345.     return;
  346.     }
  347.     
  348.                 
  349.   clippass:
  350.     R_ClipPassWallSegment (x1, x2-1);    
  351.     return;
  352.         
  353.   clipsolid:
  354.     R_ClipSolidWallSegment (x1, x2-1);
  355. }
  356.  
  357.  
  358. //
  359. // R_CheckBBox
  360. // Checks BSP node/subtree bounding box.
  361. // Returns true
  362. //  if some part of the bbox might be visible.
  363. //
  364. int    checkcoord[12][4] =
  365. {
  366.     {3,0,2,1},
  367.     {3,0,2,0},
  368.     {3,1,2,0},
  369.     {0},
  370.     {2,0,2,1},
  371.     {0,0,0,0},
  372.     {3,1,3,0},
  373.     {0},
  374.     {2,0,3,1},
  375.     {2,1,3,1},
  376.     {2,1,3,0}
  377. };
  378.  
  379.  
  380. boolean R_CheckBBox (fixed_t*    bspcoord)
  381. {
  382.     int            boxx;
  383.     int            boxy;
  384.     int            boxpos;
  385.  
  386.     fixed_t        x1;
  387.     fixed_t        y1;
  388.     fixed_t        x2;
  389.     fixed_t        y2;
  390.     
  391.     angle_t        angle1;
  392.     angle_t        angle2;
  393.     angle_t        span;
  394.     angle_t        tspan;
  395.     
  396.     cliprange_t*    start;
  397.  
  398.     int            sx1;
  399.     int            sx2;
  400.     
  401.     // Find the corners of the box
  402.     // that define the edges from current viewpoint.
  403.     if (viewx <= bspcoord[BOXLEFT])
  404.     boxx = 0;
  405.     else if (viewx < bspcoord[BOXRIGHT])
  406.     boxx = 1;
  407.     else
  408.     boxx = 2;
  409.         
  410.     if (viewy >= bspcoord[BOXTOP])
  411.     boxy = 0;
  412.     else if (viewy > bspcoord[BOXBOTTOM])
  413.     boxy = 1;
  414.     else
  415.     boxy = 2;
  416.         
  417.     boxpos = (boxy<<2)+boxx;
  418.     if (boxpos == 5)
  419.     return true;
  420.     
  421.     x1 = bspcoord[checkcoord[boxpos][0]];
  422.     y1 = bspcoord[checkcoord[boxpos][1]];
  423.     x2 = bspcoord[checkcoord[boxpos][2]];
  424.     y2 = bspcoord[checkcoord[boxpos][3]];
  425.     
  426.     // check clip list for an open space
  427.     angle1 = R_PointToAngle (x1, y1) - viewangle;
  428.     angle2 = R_PointToAngle (x2, y2) - viewangle;
  429.     
  430.     span = angle1 - angle2;
  431.  
  432.     // Sitting on a line?
  433.     if (span >= ANG180)
  434.     return true;
  435.     
  436.     tspan = angle1 + clipangle;
  437.  
  438.     if (tspan > 2*clipangle)
  439.     {
  440.     tspan -= 2*clipangle;
  441.  
  442.     // Totally off the left edge?
  443.     if (tspan >= span)
  444.         return false;    
  445.  
  446.     angle1 = clipangle;
  447.     }
  448.     tspan = clipangle - angle2;
  449.     if (tspan > 2*clipangle)
  450.     {
  451.     tspan -= 2*clipangle;
  452.  
  453.     // Totally off the left edge?
  454.     if (tspan >= span)
  455.         return false;
  456.     
  457.     angle2 = -clipangle;
  458.     }
  459.  
  460.  
  461.     // Find the first clippost
  462.     //  that touches the source post
  463.     //  (adjacent pixels are touching).
  464.     angle1 = (angle1+ANG90)>>ANGLETOFINESHIFT;
  465.     angle2 = (angle2+ANG90)>>ANGLETOFINESHIFT;
  466.     sx1 = viewangletox[angle1];
  467.     sx2 = viewangletox[angle2];
  468.  
  469.     // Does not cross a pixel.
  470.     if (sx1 == sx2)
  471.     return false;            
  472.     sx2--;
  473.     
  474.     start = solidsegs;
  475.     while (start->last < sx2)
  476.     start++;
  477.     
  478.     if (sx1 >= start->first
  479.     && sx2 <= start->last)
  480.     {
  481.     // The clippost contains the new span.
  482.     return false;
  483.     }
  484.  
  485.     return true;
  486. }
  487.  
  488.  
  489.  
  490. //
  491. // R_Subsector
  492. // Determine floor/ceiling planes.
  493. // Add sprites of things in sector.
  494. // Draw one or more line segments.
  495. //
  496. void R_Subsector (int num)
  497. {
  498.     int            count;
  499.     seg_t*        line;
  500.     subsector_t*    sub;
  501.  
  502. #ifdef RANGECHECK
  503.     if (num>=numsubsectors)
  504.     I_Error ("R_Subsector: ss %i with numss = %i",
  505.          num,
  506.          numsubsectors);
  507. #endif
  508.  
  509.     sscount++;
  510.     sub = &subsectors[num];
  511.     frontsector = sub->sector;
  512.     count = sub->numlines;
  513.     line = &segs[sub->firstline];
  514.  
  515.     if (frontsector->floorheight < viewz)
  516.     {
  517.     floorplane = R_FindPlane (frontsector->floorheight,
  518.                   frontsector->floorpic,
  519.                   frontsector->lightlevel);
  520.     }
  521.     else
  522.     floorplane = NULL;
  523.     
  524.     if (frontsector->ceilingheight > viewz 
  525.     || frontsector->ceilingpic == skyflatnum)
  526.     {
  527.     ceilingplane = R_FindPlane (frontsector->ceilingheight,
  528.                     frontsector->ceilingpic,
  529.                     frontsector->lightlevel);
  530.     }
  531.     else
  532.     ceilingplane = NULL;
  533.     
  534.     R_AddSprites (frontsector);
  535.  
  536.     while (count--)
  537.     {
  538.     R_AddLine (line);
  539.     line++;
  540.     }
  541. }
  542.  
  543.  
  544.  
  545.  
  546. //
  547. // RenderBSPNode
  548. // Renders all subsectors below a given node,
  549. //  traversing subtree recursively.
  550. // Just call with BSP root.
  551. void R_RenderBSPNode (int bspnum)
  552. {
  553.     node_t*    bsp;
  554.     int        side;
  555.  
  556.     // Found a subsector?
  557.     if (bspnum & NF_SUBSECTOR)
  558.     {
  559.     if (bspnum == -1)            
  560.         R_Subsector (0);
  561.     else
  562.         R_Subsector (bspnum&(~NF_SUBSECTOR));
  563.     return;
  564.     }
  565.         
  566.     bsp = &nodes[bspnum];
  567.     
  568.     // Decide which side the view point is on.
  569.     side = R_PointOnSide (viewx, viewy, bsp);
  570.  
  571.     // Recursively divide front space.
  572.     R_RenderBSPNode (bsp->children[side]); 
  573.  
  574.     // Possibly divide back space.
  575.     if (R_CheckBBox (bsp->bbox[side^1]))    
  576.     R_RenderBSPNode (bsp->children[side^1]);
  577. }
  578.  
  579.  
  580.